import java.util.ArrayList;
import java.util.List;

public class RadixSort {
    public static void sort(int[] array){
        int length = array.length;
        int max = 0;
        for (int i=0;i<length;i++){
            if (max<=array[i]){
                max=array[i];
            }
        }
        int times =0;
        while(max>0){
            max/=10;
            times++;
        }
        List<ArrayList> queue = new ArrayList<>();
        for (int i =0;i<10;i++){
            ArrayList q =new ArrayList();
            queue.add(q);
        }
        for (int i=0;i<times;i++){
            for (int j=0;j<length;j++){
                int x = array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
                ArrayList q=queue.get(x);
                q.add(array[j]);
                queue.set(x,q);
            }
        }
        int count =0;
        for (int j=0;j<10;j++){
            while(queue.get(j).size()>0){
                ArrayList<Integer> q =queue.get(j);
                array[count]=q.get(0);
                q.remove(0);
                count++;
            }
        }

    }

    public static void main(String[] args) {
        int[] array={3,6,8,1,2,4,9,7,0,5};
        sort(array);
        for (int i =0;i< array.length;i++){
            System.out.print(array[i]);
        }
    }
}
